// https://leetcode.cn/problems/integer-break/
// Created by ade on 2022/11/1.
// 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
// 返回 你可以获得的最大乘积
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                // 精髓：当前最大值= max(不拆分， 拆分)
                curMax = max(curMax, max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
};

int main() {
    Solution so;
    cout << so.integerBreak(10) << endl;
    return 0;
}